Devices in a network may communicate with each other via hardwired transmission lines or over the air radio frequency (RF) transmission. Networks that communicate via RF transmission are referred to as wireless networks. Mobile devices communicate via numerous RF transmissions points commonly referred to as cells, where the mobile wireless network is commonly referred to as a wireless mesh network.
Mobile devices not only communicate with each other but can also be used to access the Internet. In a wireless mesh network, there are devices that provide access to the Internet, which are commonly referred to as access points or gateways, and there are device that merely route communication (i.e., traffic) to gateways, which are commonly referred to as routers of mobile nodes. With increased use of mobile devices, there is a need to route traffic in the most efficient manner.
In an article entitled “HEAT: Scalable Routing in Wireless Mesh Networks Using Temperature Fields,” by Rainer Baumann et al., Worlds of Wireless, Mobile and Multimedia Networks, June 2007, a method was disclosed to assign a value referred to as a temperature to each mobile node, where gateways are assigned the maximum value and each mobile node is assigned a value that is a function of the values of all of its neighbors and a conductivity value. Therefore, the mobile nodes with more neighbors (i.e., more connections), tend to have higher temperatures than mobile nodes with fewer connections. Routing of mobile communications then proceeds from mobile nodes with lower temperatures to mobiles nodes with higher temperatures, always choosing the hottest node when routing, until the hottest mobile node (i.e., a gateway) is reached. Since mobile nodes with more connections tend to carry the most traffic and hence are the most congested, there is a need for a device and method that considers traffic congestion in determining routing in a mobile mesh network. The present invention is such a device and method.
In an article entitled “An Improved AODV Routing Protocol Based on the Congestion Control and Routing Repair Mechanism,” by Li Xia et al., 2009 International Conference on Communications and Mobile Computing, IEEE Computer Society, an improved AODV routing protocol for mobile ad-hoc networks (MANETs) named AODV-I was disclosed.
In an article entitled “Hop-by-hop Congestion Control over a Wireless Multi-hop Network,” by Yung Yi et al., 2009 International Conference on Communications and Mobile Computing, Proceeding of the IEEE Infocom, Hong Kong, March 2004, an algorithm to control congestion in multi-hop wireless networks.
U.S. Pat. No. 6,314,093, entitled “TRAFFIC ROUTE FINDER IN COMMUNICATIONS NETWORK,” discloses a route finder means that associates a cost to each network link. U.S. Pat. No. 6,314,093 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 6,509,898, entitled “USAGE BASED METHODS OF TRAVERSING AND DISPLAYING GENERALIZED GRAPH STRUCTURES,” discloses a method of generating a tree structure representation of a generalized graph structure for display that includes the more important links in the representation. U.S. Pat. No. 6,509,898 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,639,662, entitled “QUALITY OF SERVICE CONGESTION METRICS PROPAGATED USING ROUTING UPDATES SYSTEM AND METHOD,” discloses a device for and method of generating congestion metric information based on the utilization of a link to each of its neighbors. U.S. Pat. No. 7,639,662 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,693,064, entitled “FORWARDING PACKETS TO A DIRECTED ACYCLIC GRAPH DESTINATION USING LINK SELECTION BASED ON RECEIVED LINK METRICS,” discloses a method that utilizes path performance metrics. U.S. Pat. No. 7,693,064 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 7,843,834, entitled “USE OF MINIMAL PROPAGATION DELAY PATH TO OPTIMIZE A MESH NETWORK,” discloses a method that utilizes a minimal propagation delay path to optimize a mesh network. U.S. Pat. No. 7,843,834 is hereby incorporated by reference into the specification of the present invention.